/*
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 */

package LC0094;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// TODO 什么是二叉树的前序 中序 后序遍历?
    // 前序：中-左-右
    // 中序：左-中-右
    // 后续：左-右-中
// 遍历过程天然具有递归的性质
// 递归调用 inorder(root.left) 来遍历 root 节点的左子树，
// 然后将 root 节点的值加入答案，
// 再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，
// 递归终止的条件为碰到空节点。

class Solution1 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return; // TODO 返回了什么？
        }
        // 从根结点开始
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}
// 二叉树深度优先遍历
    //前序遍历： 144.二叉树的前序遍历
    //后序遍历： 145.二叉树的后序遍历
    //中序遍历： 94.二叉树的中序遍历
//二叉树广度优先遍历
    //层序遍历：102.二叉树的层序遍历
